Pada tahun 535, Maharaja Justinian I mengembalikan Sicily kepada empayar Byzantine yang kini diperintah dari secara ekslusif daripada Constantinople. Apabila kuasa Byzantine mula lemah di bahagian Barat, Sicilia telah diserang oleh tentera Arab semasa pemerintahan Khalifah Uthman pada tahun 652. Bagaimanapun, serangan pertama ini hanya sementara apabila ia kemudian ditinggalkan. Menjelang akhir abad ke-7, dengan penaklukkan Umayyah ke atas Afrika Utara, Arab telah menawan kota pelabuhan yang berhampiran Carthage, membolehkan orang-orang Arab untuk membina limbungan kapal dan pangkalan tetap bagi melancarkan serangan yang lebih hebat.[7]

Sekitar tahun 700, pulau Pantelleria telah ditawan oleh Arab, dan hanya perpecahan dalam kalangan orang Arab yang menghalang serangan ke atas Sicily. Sebaliknya, perjanjian-perjanjian perdagangan telah diatur dengan Byzantine, dan para pedagang Arab telah dibenarkan berniaga barangan di pelabuhan-pelabuhan Sicily. Serangan dari armada-armada Muslim berlaku pada tahun 703, 728, 729, 730, 731, 733 dan 734,dengan dua serangan terakhir menerima tentangan hebat daripada Byzantine.

Ekspedisi penaklukan pertama telah dilancarkan pada tahun 740, tahun di mana putera Muslim bernama [Habib]], telah mengambil bahagian dalam serangan pada tahun 728, berjaya menawan Siracusa. Meskipun bersedia untuk menakluk seluruh pulau, mereka terpaksa kembali ke [Tunisia]] di sebabkan pemberontakkan oleh orang Barbar. Serangan kedua pada tahun 752 bertujuan untuk menjarah bandar yang sama.